package com.tgy.algorithm._经典题目01._review;

import java.util.Arrays;

public class _查找第k小的值 {


    public static int findKValue(int[] nums,int k) {
        if (nums == null || nums.length < k) {
            throw new RuntimeException("数据有问题");
        }

        int len = nums.length;
        int left = 0;
        int right = len - 1;
        k = k - 1;

        while (true) {

            int randomIndex = (int) (Math.random() * ((right - left) + 1)) + left;
            swap(nums,randomIndex,right);
            int[] equalRange = findEqualRange(nums, left, right);

            int leftEq = equalRange[0];
            int rightEq = equalRange[1];

            if (leftEq <= k && k <= rightEq) {
                return nums[leftEq];
            }else if(k > rightEq) {
                left = rightEq + 1;
            }else {
                right = leftEq - 1;
            }
        }

    }

    public static void swap(int[] nums,int one, int two) {
        int tmp = nums[one];
        nums[one] = nums[two];
        nums[two] = tmp;
    }

    public static int[] findEqualRange(int[]nums,int left,int right) {

        int[] ints = new int[2];
        int leftIndex = left - 1;
        int rightIndex = right - 1;
        int index = left;
        int value = nums[right];
        while (index <= rightIndex) {

            if (nums[index] < value) {
                if (leftIndex + 1 != index) {
                    swap(nums,leftIndex+1,index);
                }
                index++;
                leftIndex++;
            }else if (nums[index] == value) {
                index++;
            }else {
                swap(nums,index,rightIndex--);
            }
        }

        swap(nums,rightIndex+1,right);
        ints[0] = leftIndex+1;
        ints[1] = rightIndex+1;
        return ints;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3,2,4,3,2,5,4,1,6,4};
        int k = 3;
        int kValue = findKValue(nums, k);
        System.out.println(kValue);
        int[] cp01 = Arrays.copyOf(nums, nums.length);
        Arrays.sort(cp01);
        System.out.println(Arrays.toString(cp01));
        System.out.println(cp01[k - 1]);

    }
}
